<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<meta name="viewport" content="initial-scale=1, maximum-scale=1, user-scalable=0, viewport-fit=cover" />
	<title>link-list</title>
</head>
<body>
<script>
// 链表中每一个节点
class LinkNode {
	constructor(value) {
		this.value = value;
		this.next = null;
	}
}

// 单向链表
class LinkList {
	constructor(value) {
		if (value) {
			this.head = new LinkNode(value);
			this.size = 1;
		}
		else {
			this.head = null;
			this.size = 0;
		}
	}

	getSize() {
		return this.size;
	}

	pushNode(value) {
		const newNode = new LinkNode(value);
		if (!this.head) {
			this.head = newNode
		}
		else {
			let currentNode = this.head;
			while (currentNode.next) currentNode = currentNode.next;
			currentNode.next = newNode;
		}
		this.size++;
		return newNode;
	}

	searchNode(index) {
		if (index < 0 || index >= this.size) return null; // 排除 index 范围
		let findNode = this.head;
		let i = 0;
		while (i < index) {
			findNode = findNode.next;
			i++;
		}

		return findNode;
	}

	insertNode(index, value) {
		if (index < 0 || index > this.size) return;
		const newNode = new LinkNode(value);
		// 头
		if (index === 0) {
			newNode.next = this.head;
			this.head = newNode;
		}
		// 尾
		else if (index === this.size) {
			const findNode = this.searchNode(this.size - 1)
			findNode.next = newNode;
		}
		// 中间
		else {
			const prevNode = this.searchNode(index - 1);
			const currentNode = prevNode.next;
			newNode.next = currentNode;
			prevNode.next = newNode;

		}
		this.size++;
		return newNode;
	}

	removeNode(index) {
		if (index < 0 || index >= this.size) return;
		// 头
		if (index === 0) {
			const nextNode = this.head.next;
			this.head = nextNode;
		}
		// 尾
		else if (index === this.size - 1) {
			const prevNode = this.searchNode(index - 1);
			prevNode.next = null;
		}
		// 中间
		else {
			const prevNode = this.searchNode(index - 1);
			const nextNode = prevNode.next.next;
			prevNode.next = nextNode;
		}
		this.size--;
	}

	// [value, value, value, ...]
	toArr() {
		const arr = [];
		let currentNode = this.head;

		while (currentNode) {
			arr.push(currentNode.value)
			currentNode = currentNode.next
		}

		return arr;
	}
	// value1 -> value2 -> value3
	toString() {
		return this.toArr().join(' -> ')
	}

	// 反转
	reverseNodeList() {
		if (this.size <= 1) return this;
		let prevNode = null;
		let currentNode = this.head;
		let nextNode = currentNode.next;

		while (currentNode) {
			currentNode.next = prevNode; // 核心
			prevNode = currentNode;
			currentNode = nextNode;
			if (nextNode) {
				nextNode = currentNode.next;
			}
			else {
				this.head = prevNode;
			}
		}

		return this;
	}
}


const linkList = new LinkList('张三')
linkList.pushNode('李四')
linkList.pushNode('王五')
linkList.pushNode('赵六')
// linkList.insertNode(-1, '超人')
// linkList.removeNode(1)
// linkList.reverseNodeList();
// console.log(`linkList------`, linkList.toArr())
// console.log(`linkList------`, linkList.toString())
// console.log(`searchNode-----`, linkList.searchNode(3))
</script>
</body>
</html>
